//给你一个 只包含正整数 的 非空 数组与矩阵 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
//
//
//
// 示例 1：
//
//
//输入：nums = [1,5,11,5]
//输出：true
//解释：数组可以分割成 [1, 5, 5] 和 [11] 。
//
// 示例 2：
//
//
//输入：nums = [1,2,3,5]
//输出：false
//解释：数组不能分割成两个元素和相等的子集。
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 200
// 1 <= nums[i] <= 100
//
//
// Related Topics 数组与矩阵 动态规划 👍 1712 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function canPartition(nums: number[]): boolean {

    const sum: number = nums.reduce((pre, cur) => pre + cur);
    if (sum % 2 === 1) return false;
    const bagSize: number = sum / 2;
    const goodsNum: number = nums.length;
    const dp: number[] = new Array(bagSize + 1).fill(0);
    for (let i = 0; i < goodsNum; i++) {
        //? j >= nums[i]也保证数组不越界
        for (let j = bagSize; j >= nums[i]; j--) {
            //? 这里以要寻找的数作为背包容量 因为本题中每一个元素的数值既是重量，也是价值。也因为遍历过程中的数不会超过此数
            dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
        }
    }
    return dp[bagSize] === bagSize;
};
//leetcode submit region end(Prohibit modification and deletion)
